/*
 * @Author: HuanXX shy2757539057@163.com
 * @Date: 2024-10-01 12:09:17
 * @LastEditors: HuanXX
 * @LastEditTime: 2024-10-01 12:11:56
 * @Description: file content
 */
package dp.matrixchain;
public class Main {
    public static void main(String[] args) {
        int[] p = new int[] { 30, 35, 15, 5, 10, 20, 25 };
        int[][] m = new int[p.length][p.length];
        int[][] s = new int[p.length][p.length];
        matrixChain(p, p.length - 1, m, s);
        // System.out.println(Arrays.deepToString(m));
        // System.out.println(Arrays.deepToString(s));
        traceBack(1, p.length - 1, s);
    }

    public static void traceBack(int begin, int end, int[][] locationk) {
        if (begin == end) {
            return;
        }
        traceBack(begin, locationk[begin][end], locationk);
        traceBack(locationk[begin][end] + 1, end, locationk);
        System.out.printf("Multiply A %d,%d\n", begin, locationk[begin][end]);
        System.out.printf("and A %d,%d\n", locationk[begin][end] + 1, end);
    }

    public static void matrixChain(int[] matrixsize, int matrixchainsize, int[][] minvalue, int[][] locationk) {
        // 为了方便二维数组都是从1开始计数
        for (int range = 1; range <= matrixchainsize; range++) {
            minvalue[range][range] = 0;
            // 单个矩阵链相乘的最优值为0
        }
        for (int range = 2; range <= matrixchainsize; range++) {
            // r是矩阵链的长度，上面的循环1的情况已经处理完成
            for (int i = 1; i <= matrixchainsize - (range - 1); i++) {
                // 遍历所有矩阵链为r的情况
                int j = i + (range - 1);
                minvalue[i][j] = minvalue[i][i] + minvalue[i + 1][j] + matrixsize[i - 1] * matrixsize[i] * matrixsize[j];
                locationk[i][j] = i;
                // 上面的情况是k=i,先初始化方便循环内比较
                for (int k = i + 1; k < j; k++) {
                    int temp = minvalue[i][k] + minvalue[k + 1][j] + matrixsize[i - 1] * matrixsize[k] * matrixsize[j];
                    // 选择值最小的那个，要做比较因此先暂存
                    if (temp < minvalue[i][j]) {
                        // 只有小于才更改
                        minvalue[i][j] = temp;
                        locationk[i][j] = k;
                    }
                }
            }
        }
    }
}